package com.smart.framework.util;

import java.util.Random;

/**
 * <p><b>Description:</b>  TODO
 * <p><b>Company:</b>
 *
 * @author created by Jesse Xu at 15:07 on 2019/9/23
 * @version V0.1
 * @classNmae CollectionUtils
 */
public class ArrayUtils {
    public static boolean isEmpty(Object[] array) {
        if (array != null && array.length != 0) {
            return false;
        }
        return true;
    }

    public static boolean isNotEmpty(Object[] array) {
        if (array != null && array.length != 0) {
            return true;
        }
        return false;
    }

    /**
     * 冒泡排序
     * @param a
     * @return 排序好的数组
     */
    public static int[] bubbleSort(int[] a){
        int n = a.length;
        if(n<=1){
            return a;
        }
        for (int i = n;i>0;i--){
            for (int j = 1;j<i;j++){
                if(a[j-1]>a[j]){
                    //swap
                    int temp =a[j-1];
                    a[j-1] = a[j];
                    a[j] = temp;
                }
            }
        }
        return a;
    }

    public static int[] quickSort(int[] a){
       int[] res = doQuickSort(a,0,a.length-1);
        return res;
    }

    public static int[] doQuickSort(int[] a,int start,int end){

        if(start>=end){   //注意出递归条件
            return a;
        }
        //选取一个基准点
        int base =a[end];
        int i = start;
//        int j = end -1;   //这里可以优化,徒增了下面很多判断
        int j = end ;
        while(i<j){
            while (a[i]<base&&i<end){
                i++;
            }
            while (a[j]>=base&&j>start){  //注意条件
                j--;
            }
            if(i<j){
                int temp =a[i];
                a[i] =a[j];
                a[j] = temp;
            }
        }
//        if(a[i]>base){
//            a[end] = a[i];
//            a[i] = base;
//        }
        a[end] = a[i];
        a[i] = base;
        doQuickSort(a,start,i-1);
        doQuickSort(a,i+1,end);
        return a;
    }

    // 快速排序，a是数组，n表示数组的大小
    public static void quickSort(int[] a, int n) {
        quickSortInternally(a, 0, n-1);
    }

    private static void quickSortInternally(int[] a, int p, int r) {
        if (p >= r) return;

        int q = partition(a, p, r); // 获取分区点
        quickSortInternally(a, p, q-1);
        quickSortInternally(a, q+1, r);
    }

    //一种快排分区方法
    private static int partition(int[] a, int p, int r) {
        int pivot = a[r];
        int i = p;
        for(int j = p; j < r; ++j) {
            if (a[j] < pivot) {
                if (i == j) {
                    ++i;
                } else {
                    int tmp = a[i];
                    a[i++] = a[j];
                    a[j] = tmp;
                }
            }
        }

        int tmp = a[i];
        a[i] = a[r];
        a[r] = tmp;

        System.out.println("i=" + i);
        return i;
    }


    /**
     * 计数排序,桶排序的特殊情况,将桶的范围缩小为1即为计数排序,a是数组，假设数组中存储的都是非负整数。
     *
     * @return
     */
    public static int[] countingSort(int[] a) {
        int n = a.length;
        if (n <= 1)
            return a;
        // 查找数组中数据的范围，构造m个桶
        int max = a[0];
        for (int i = 0; i < n; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        // 申请一个计数数组c，下标大小[0,max]
        int[] c = new int[max + 1];
        for (int i = 0; i <= max; i++) {
            c[i] = 0;
        }
        // 计算每个元素的个数，
        for (int i = 0; i < n; ++i) {
            c[a[i]]++;
        }
        //累加 对a数组各个取值计数
        for (int i = 1; i <=max; i++) {
            c[i] = c[i-1] + c[i];
        }
        // 临时数组r，存储排序之后的结果 int[] r = new int[n];
        int[] r = new int[n];
        // 计算排序的关键步骤
        for (int i = n - 1; i >= 0; i--) {
            int index = c[a[i]] - 1;
            r[index] = a[i];
            c[a[i]]--;
        }
        // 将结果拷贝给a数组

        return r;
    }

    public static int[] copyOf(int[] a){
        int n = a.length;
        int[] r = new int[n];
        for (int i = 0; i < n; ++i) {
            r[i] = a[i];
        }
        return r;
    }

    public static void print(int[] a){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < a.length; ++i) {
            sb.append(a[i] + " ");
        }
        System.out.println(sb.toString());
    }
    public static void main(String[] args) {
        int len = 100;
        int[] arr=new int[len];
        Random rand = new Random();
        int bound =100;
        for (int i = 0;i<arr.length;i++){
            arr[i] =  rand.nextInt(bound);
        }
//        print(arr);
        int[] bubble_arr = copyOf(arr);
        int[] counting_arr = copyOf(arr);
        int[] quickSort_arr = copyOf(arr);
        long start=0,end=0;
//        long start = System.currentTimeMillis();
//        int[] bubble_res =bubbleSort(bubble_arr);
//        long end = System.currentTimeMillis();
//        System.out.println("bubble sort : " + (end-start)+"ms");

//        start = System.currentTimeMillis();
//        int[] counting_res =countingSort(counting_arr);
//        end = System.currentTimeMillis();
//        System.out.println("counting sort : " + (end-start)+"ms");

        start = System.currentTimeMillis();
//        quickSort_arr =new int[]{0,1};
        int[] quickSort_res =quickSort(quickSort_arr);
        end = System.currentTimeMillis();
;
        print(quickSort_arr);
        System.out.println("quick sort : " + (end-start)+"ms");
    }
}
